home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_5.7 / XSGLL / SGL_TO_P.C < prev    next >
C/C++ Source or Header  |  1999-09-11  |  11KB  |  345 lines
  1. /* 
  2.  * sgl_to_p.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * SGL_TO_POLY
  11.  *
  12.  * routines to construct ordered, cyclic array of vertices, given
  13.  * a segm group list containing elements in the order of increasing dij
  14.  */
  15.  
  16. #include <stdio.h>
  17. #include <math.h>
  18.  
  19. #include "lldef.h"
  20. #include "xsgll.h"
  21.  
  22.  
  23. #undef    DEBUG_VA
  24. #undef    DEBUG_MERGE
  25.  
  26. /* globals */
  27. extern int MERGE;
  28.  
  29. /*
  30.  * merge two successive ("current" and "next") segments 
  31.  * sharing a common vertex and delete "current" segment from list
  32.  */
  33. void
  34. merge_segm (segm, list, cSegm, nSegm, nva, MergeDirn)
  35.      struct Segm *segm;
  36.      struct linklist *list;
  37.      struct Segmtype *cSegm, *nSegm;
  38.      int *nva;
  39.      Boolean MergeDirn;
  40. {
  41.   if (MergeDirn == Forward) {
  42.     (segm + nSegm->segm_ind)->ptO.x = (segm + cSegm->segm_ind)->ptO.x;
  43.     (segm + nSegm->segm_ind)->ptO.y = (segm + cSegm->segm_ind)->ptO.y;
  44.   }
  45.   else {
  46.     (segm + nSegm->segm_ind)->ptF.x = (segm + cSegm->segm_ind)->ptF.x;
  47.     (segm + nSegm->segm_ind)->ptF.y = (segm + cSegm->segm_ind)->ptF.y;
  48.   }
  49.  
  50.   llprevious (list);
  51.   lldelete (list);
  52.   *nva -= 2;
  53. }
  54.  
  55.  
  56. /*
  57.  * swap two points
  58.  */
  59. Boolean
  60. swap_pts (pt1, pt2)
  61.      struct spoint *pt1, *pt2;
  62. {
  63.   struct spoint temp_pt;
  64.  
  65.  
  66.   temp_pt.x = pt2->x;
  67.   temp_pt.y = pt2->y;
  68.  
  69.   pt2->x = pt1->x;
  70.   pt2->y = pt1->y;
  71.   pt1->x = temp_pt.x;
  72.   pt1->y = temp_pt.y;
  73.  
  74.   return (True);
  75. }
  76.  
  77.  
  78. /*
  79.  * construct an ordered, cyclic array of vertices from the endpoints
  80.  * of the segments in a given SGL in which these segments are stored
  81.  * in order of increasing dij; 
  82.  * the sense of the resulting closed polygon is determined by the 
  83.  * orientation of the reference segment at the top of the list;
  84.  * by construction (see sall.c), all segments in a given SGL have 
  85.  * similar slopes (not necessarily of the same sign, as in the case
  86.  * where segments which are nearly parallel with the x-axis but point 
  87.  * into different quadrants);
  88.  *
  89.  * establish a reference orientation as follows:
  90.  * let the vector vr:=( r_delx, r_dely ) define the reference segment;
  91.  * the slope m of the reference segment is given by m=r_dely/r_delx;
  92.  * let the vector vr_perp define the line segment perpendicular to vr
  93.  * with length equal to that of vr; since the slope of the perpendicular
  94.  * line segment, m_perp, is given by m_perp=-1.0/m=r_delx/(-r_dely),
  95.  * one has: xf_perp = xo - r_dely and yf_perp = yo + r_delx; the sign of
  96.  * the cross product r_cof:=(vr x vr_perp) is taken to define the 
  97.  * reference orientation (note: this reference cross product is by
  98.  * construction non-zero!);
  99.  * the orientation of all other segments in the SGL, represented by the
  100.  * vector vs:=( (ptF.x-ptO.x), (ptF.y-ptO.y) ), is compared with the
  101.  * reference orientation as follows:
  102.  * construct a line segment of slope m_perp(!) containing ptO=(c_xo, c_yo)
  103.  * of the current segment; since the length of this line segment is 
  104.  * immaterial, define vs_perp by choosing the following coordinates
  105.  * for the endpoint: c_xf_perp = c_xo - r_dely, c_yf_perp = c_yo + r_delx;
  106.  * finally, evaluate the cross product (vs x vs_perp) and compare its
  107.  * sign to the reference orientation: swap enpoints of current segment
  108.  * if indicated;
  109.  */
  110. double
  111. construct_va (segm, list, nva, va)
  112.      struct Segm *segm;
  113.      struct linklist *list;
  114.      int *nva;
  115.      struct spoint *va;
  116. {
  117.   struct Segmtype *rSegm, *cSegm, *nSegm;
  118.  
  119.   long r_cof, c_cof;
  120.   long xo, yo, xf, yf;
  121.   long r_delx, r_dely, c_delx, c_dely;
  122.   long xc_o, yc_o, xc_f, yc_f;
  123.   long xn_o, yn_o, xn_f, yn_f;
  124.   int sr_cof, sc_cof;
  125.   double av_azimuth;
  126.   double r_slp, c_slp, av_slope, dnull = 0.0;
  127.   int sr_slp, sc_slp;
  128.  
  129.   int i, n, nn;
  130.   Boolean SwapStat;
  131.  
  132.  
  133. /*
  134.  * scan SGL (assumed to contain segments in increasing order of dij):
  135.  * inspect each segment and bring all segments into the same orientation,
  136.  * arbitrarily chosen to be that of the segment at the top of the list
  137.  */
  138.   llhead (list);
  139.   rSegm = (struct Segmtype *) list->clp->item;
  140.   xo = (long) (segm + rSegm->segm_ind)->ptO.x;
  141.   yo = (long) (segm + rSegm->segm_ind)->ptO.y;
  142.   xf = (long) (segm + rSegm->segm_ind)->ptF.x;
  143.   yf = (long) (segm + rSegm->segm_ind)->ptF.y;
  144.   r_delx = xf - xo;
  145.   r_dely = yf - yo;
  146.  
  147. /*
  148.  * reference orientation
  149.  */
  150.   r_cof = (-r_dely) * r_dely - (r_delx * r_delx);
  151.   sr_cof = SIGN (r_cof);
  152.  
  153.   if ((sr_cof == 0)) {
  154.     printf ("\n...vanishing cross product for ref Segm: ");
  155.     printf ("unknown condition!!\n");
  156.     return (dnull);
  157.   }
  158.  
  159.  
  160. #ifdef DEBUG_VA
  161.   printf ("\n\n...end points of reference segment:\n");
  162.   printf ("    ptO.x = %d, ptO.y = %d\n",
  163.           (segm + rSegm->segm_ind)->ptO.x, (segm + rSegm->segm_ind)->ptO.y);
  164.   printf ("    ptF.x = %d, ptF.y = %d\n",
  165.           (segm + rSegm->segm_ind)->ptF.x, (segm + rSegm->segm_ind)->ptF.y);
  166.   printf ("    sign( reference cross_prd ) = %d\n", sr_cof);
  167. #endif
  168.  
  169.  
  170.   while (llnext (list) == True) {
  171.     SwapStat = False;
  172.  
  173.     cSegm = (struct Segmtype *) list->clp->item;
  174.     xo = (long) (segm + cSegm->segm_ind)->ptO.x;
  175.     yo = (long) (segm + cSegm->segm_ind)->ptO.y;
  176.     xf = (long) (segm + cSegm->segm_ind)->ptF.x;
  177.     yf = (long) (segm + cSegm->segm_ind)->ptF.y;
  178.     c_delx = xf - xo;
  179.     c_dely = yf - yo;
  180.     c_cof = (-r_dely) * c_dely - r_delx * c_delx;
  181.     sc_cof = SIGN (c_cof);
  182.  
  183.     if ((sc_cof == 0)) {
  184.       printf ("\n...vanishing cross product for cur Segm: ");
  185.       printf ("unknown condition!!\n");
  186.       return (dnull);
  187.     }
  188.  
  189.  
  190. #ifdef DEBUG_VA
  191.     printf ("\n...current end points (prior to swap):\n");
  192.     printf ("    ptO.x = %d, ptO.y = %d\n",
  193.           (segm + cSegm->segm_ind)->ptO.x, (segm + cSegm->segm_ind)->ptO.y);
  194.     printf ("    ptF.x = %d, ptF.y = %d\n",
  195.           (segm + cSegm->segm_ind)->ptF.x, (segm + cSegm->segm_ind)->ptF.y);
  196.     printf ("    sign( current cross_prd ) = %d\n", sc_cof);
  197. #endif
  198.  
  199.  
  200.     if (sc_cof != sr_cof)
  201.       SwapStat = swap_pts (&((segm + cSegm->segm_ind)->ptO),
  202.                            &((segm + cSegm->segm_ind)->ptF));
  203.  
  204.  
  205. #ifdef DEBUG_VA
  206.     if (SwapStat == True) {
  207.       printf ("...end points swapped:\n");
  208.       printf ("    ptO.x = %d, ptO.y = %d\n",
  209.               (segm + cSegm->segm_ind)->ptO.x,
  210.               (segm + cSegm->segm_ind)->ptO.y);
  211.       printf ("    ptF.x = %d, ptF.y = %d\n",
  212.               (segm + cSegm->segm_ind)->ptF.x,
  213.               (segm + cSegm->segm_ind)->ptF.y);
  214.     }
  215. #endif
  216.  
  217.   }
  218.  
  219.  
  220.  
  221. /*
  222.  * now that all segm in SGL have the same orientation, merge
  223.  * segments sharing a common vertex; that is, replace two successive
  224.  * segments {(ptO1.x, ptO1.y), (ptF1.x, ptF1.y)} and
  225.  * {(ptO2.x, ptO2.y), (ptF2.x, ptF2.y)} sharing the vertex
  226.  * (ptF1.x, ptF1.y) = (ptO2.x, ptO2.y) or the vertex
  227.  * (ptO1.x, ptO1.y) = (ptF2.x, ptF2.y) by the new 
  228.  * segment {(ptO1.x, ptO1.y), (ptF2.x, ptF2.y)}; this is equivalent
  229.  * to removing "interior" points from the polygon of segment
  230.  * endpoints to be constructed below;
  231.  * given that each SGL contains elements in the order of increasing dij
  232.  * the search for matching vertices can be restricted to pairs of
  233.  * successive sgements in the list;
  234.  */
  235.   if (MERGE == 1) {
  236.     llhead (list);              /* search for shared vertices */
  237.     cSegm = (struct Segmtype *) list->clp->item;
  238.  
  239.     while (llnext (list) == True) {
  240.       xc_o = (long) (segm + cSegm->segm_ind)->ptO.x;
  241.       yc_o = (long) (segm + cSegm->segm_ind)->ptO.y;
  242.       xc_f = (long) (segm + cSegm->segm_ind)->ptF.x;
  243.       yc_f = (long) (segm + cSegm->segm_ind)->ptF.y;
  244.  
  245.       nSegm = (struct Segmtype *) list->clp->item;
  246.       xn_o = (long) (segm + nSegm->segm_ind)->ptO.x;
  247.       yn_o = (long) (segm + nSegm->segm_ind)->ptO.y;
  248.       xn_f = (long) (segm + nSegm->segm_ind)->ptF.x;
  249.       yn_f = (long) (segm + nSegm->segm_ind)->ptF.y;
  250.  
  251. #ifdef DEBUG_MERGE
  252.       printf ("\n");
  253.       printf ("...(xc_o,yc_o): (%ld, %ld)", xc_o, yc_o);
  254.       printf ("...(xc_f,yc_f): (%ld, %ld)\n", xc_f, yc_f);
  255.       printf ("...(xn_o,yn_o): (%ld, %ld)", xn_o, yn_o);
  256.       printf ("...(xn_f,yn_f): (%ld, %ld)\n", xn_f, yn_f);
  257. #endif
  258.       if ((xc_f == xn_o) && (yc_f == yn_o)) {
  259. #ifdef DEBUG_MERGE
  260.         printf ("\n...shared vertex found: ");
  261.         printf (" (%ld, %ld)", xc_f, yc_f);
  262.         printf (" -> merge Forward\n");
  263. #endif
  264.         merge_segm (segm, list, cSegm,
  265.                     nSegm, nva, Forward);
  266.       }
  267.       else if ((xc_o == xn_f) && (yc_o == yn_f)) {
  268. #ifdef DEBUG_MERGE
  269.         printf ("\n...shared vertex found: ");
  270.         printf (" (%ld, %ld)", xc_f, yc_f);
  271.         printf (" -> merge Reverse\n");
  272. #endif
  273.         merge_segm (segm, list, cSegm,
  274.                     nSegm, nva, Reverse);
  275.       }
  276.       cSegm = nSegm;
  277.     }
  278.   }
  279.  
  280.  
  281. /*
  282.  * construct an ordered, cyclic vertex array from the segm endpoints;
  283.  * in same pass through list, compute the average value of segm slopes;
  284.  * recall that atan() returns a value in [-PI/2, PI/2];
  285.  */
  286.   n = *nva - 1;                 /* last array index */
  287.   nn = *nva - 2;
  288.  
  289.   llhead (list);
  290.   rSegm = (struct Segmtype *) list->clp->item;
  291.   r_slp = (double) fslope ((segm + rSegm->segm_ind)->ptO,
  292.                            (segm + rSegm->segm_ind)->ptF);
  293.   if ((sr_slp = SIGN (r_slp)) == 0)
  294.     sr_slp = 1;
  295.  
  296.  
  297. /* close polygon: first & last vertices identical */
  298.   (va + n)->x = (segm + rSegm->segm_ind)->ptO.x;
  299.   (va + n)->y = (segm + rSegm->segm_ind)->ptO.y;
  300.  
  301.   av_azimuth = av_slope = 0.0;
  302.   i = 0;
  303.   do {
  304.     cSegm = (struct Segmtype *) list->clp->item;
  305.  
  306.     (va + i)->x = (segm + cSegm->segm_ind)->ptO.x;
  307.     (va + i)->y = (segm + cSegm->segm_ind)->ptO.y;
  308.     (va + nn - i)->x = (segm + cSegm->segm_ind)->ptF.x;
  309.     (va + nn - i)->y = (segm + cSegm->segm_ind)->ptF.y;
  310.  
  311.     c_slp = (double) fslope ((segm + cSegm->segm_ind)->ptO,
  312.                              (segm + cSegm->segm_ind)->ptF);
  313.     if ((sc_slp = SIGN (c_slp)) == 0)
  314.       sc_slp = 1;
  315.  
  316.  
  317.     if (sc_slp == sr_slp)
  318.       av_azimuth += atan (c_slp);
  319.     else {
  320.       xo = (long) (segm + cSegm->segm_ind)->ptO.x;
  321.       yo = (long) (segm + cSegm->segm_ind)->ptO.y;
  322.       xf = (long) (segm + cSegm->segm_ind)->ptF.x;
  323.       yf = (long) (segm + cSegm->segm_ind)->ptF.y;
  324.       c_delx = xf - xo;
  325.       c_dely = yf - yo;
  326.  
  327.       if (SIGN (r_dely) != SIGN (c_dely))  /* horizontal */
  328.         av_azimuth += atan (c_slp);
  329.  
  330.       else if (SIGN (r_delx) != SIGN (c_delx)) {  /* vertical */
  331.         if (sc_slp < 0)
  332.           av_azimuth += (PI + atan (c_slp));
  333.         else if (sc_slp > 0)
  334.           av_azimuth += (-PI + atan (c_slp));
  335.       }
  336.     }
  337.     i++;
  338.  
  339.   } while (llnext (list) == True);
  340.  
  341.   av_azimuth /= (double) list->listlength;
  342.   av_slope = tan (av_azimuth);
  343.   return (av_slope);
  344. }
  345.